package com.ryujung.array.leetCode_1051;

import java.util.Arrays;

/**
 * 学校在拍年度纪念照时，一般要求学生按照 非递减 的高度顺序排列。
 * <p>
 * 请你返回能让所有学生以 非递减 高度排列的最小必要移动人数。
 * 示例：
 * 输入：heights = [1,1,4,2,1,3]
 * 输出：3
 * 提示：
 * <p>
 * 1 <= heights.length <= 100
 * 1 <= heights[i] <= 100
 *
 * @author RyuJung
 * @date 2020-2-26 14:10
 */
public class Solution {
    //排序对比法,时间复杂度最低也有 O(NlogN)O(NlogN)。
    public static int heightChecker1(int[] heights) {
        int[] temp = heights.clone();
        Arrays.sort(temp);
        int count = 0;
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] != temp[i]) {
                count++;
            }
        }
        return count;
    }

    /**
     * 利用桶的思想,将相同的数放在同一个桶位, 桶位记录数量
     * 从桶中取出元素时，元素的排列顺序就是非递减的，然后与heights中的元素比较，如果不同，计算器就加1
     * 由于heights>=1,所以0号桶位值必定为0
     * 循环判断并取出桶中的元素,将该元素和原数组的元素比较,不同+1,相同就继续循环
     *
     * @param heights
     * @return
     */
    public static int heightChecker2(int[] heights) {
        int[] arr = new int[101];
        for (int i: heights) {
            //将原数组中所有值放进相应的桶中, 统计数量
            arr[i]++;
        }
        //定义记录结果需要的计数器
        int count = 0;
        //考虑桶位就是元素的值,所以0号桶位必然没有值, 桶位要达到100,需要0~101才能装0~100之间的值
        for (int i = 0, j = 0; i < arr.length; i++) {
            //将所有桶中数量>0的值取出来(已经是非降序)
            while (arr[i] > 0) {
                //与原数组的每一位进行比较,比较完毕再取出arr的下一个值
                if (heights[j++] != i) {
                    count++;
                }
                arr[i]--;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int res = heightChecker2(new int[]{1, 1, 4, 2, 1, 3,});
        System.out.println(res);
    }
}
